public class Sort {
    /**直接插入排序
     * 稳定性：稳定的排序
     *时间复杂度：O(N^2)
     *空间复杂度：O(1)，它是一种稳定的排序算法
     * @param array
     */
    public static void insertSort(int[] array){
        for(int i=1;i<array.length;i++){
            int tmp=array[i];
            int j=i-1;
            for(;j>=0;j--){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    /**选择排序
     *时间复杂度：O(N^2)
     *空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    //方法1
//    public static void selectSort(int[] array){
//        for(int i=0;i<array.length;i++){
//            int min=i;
//            for(int j=i+1;j<array.length;j++){
//                if(array[min]>array[j]){
//                    min=j;
//                }
//            }
//            swap(array,i,min);
//        }
//    }
    //方法2
    public static void selectSort(int[] array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
            for(int i=left+1;i<=right;i++){
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array,left,minIndex);
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    /**堆排序
     *  时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     *  稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end-1);
            end--;
        }
    }
    private static void createHeap(int[] array){
        for(int parent=(array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);
        }
    }
    private static void siftDown(int[] array,int parent,int len){
        int child=2*parent+1;
        while(child<len){
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }

    /**冒泡排序
     * 时间复杂度：O(N^2)
     * 以下代码如果有序，最好情况下，时间复杂度为O(N)
     *  空间复杂度：O(1)
     *  稳定性：稳定
     * @param array
     */
    public static void bubbleSort(int[] array){
        for(int i=0;i<array.length-1;i++){
            boolean flg=false;
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(!flg){
                break;
            }
        }
    }

    /**快速排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(logN)
     * 稳定性：不稳定
     * @param array
     */

    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int par=partition(array,left,right);
        quick(array,left,par-1);
        quick(array,par+1,right);
    }
    //1. Hoare版
//    private static int partition(int[] array,int start,int end){
//        int i=start;
//        int pivot=array[start];
//        while(start<end){
//            while(start<end&&array[end]>=pivot){
//                end--;
//            }
//            while(start<end&&array[start]<=pivot){
//                start++;
//            }
//            swap(array,start,end);
//        }
//        swap(array,i,start);
//        return start;
//    }
    //2.挖坑版
    private static int partition(int[] array,int start,int end){
        int pivot=array[start];
        while(start<end){
            while(start<end&&array[end]>=pivot){
                end--;
            }
            array[start]=array[end];
            while(start<end&&array[start]<=pivot){
                start++;
            }
            array[end]=array[start];
        }
        array[start]=pivot;
        return start;
    }

    /**
     * 归并排序
     * 时间复杂度：O(n*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param array
     */
    //递归
    public static void mergeSort1(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }

    private static void mergeSortFunc(int[] array, int left, int right) {
        if(left==right){
            return;
        }
        int mid=(left+right)/2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }

    private static void merge(int[] array, int left, int right, int mid) {
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int[] tmpArr=new int[right-left+1];
        int k=0;
        while(s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                tmpArr[k++]=array[s1++];
            }else{
                tmpArr[k++]=array[s2++];
            }
        }
        while(s1<=e1){
            tmpArr[k++]=array[s1++];
        }
        while(s2<=e2){
            tmpArr[k++]=array[s2++];
        }
        for(int i=0;i<tmpArr.length;i++){
            array[i+left]=tmpArr[i];
        }
    }
    //非递归
    public static void mergeSort(int[] array){
        int gap=1;
        while(gap<array.length){
            for(int i=0;i<array.length;i+=2*gap){
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                if(mid>array.length){
                    mid=array.length-1;
                }
                if(right>array.length){
                    right=array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap*=2;
        }
    }
}
